package leetcode.binarytree;

import leetcode.TreeNode;
import leetcode.TreeNodeUtil;

/**
 * @author Cheng Jun
 * Description: 给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
 * 每条从根节点到叶节点的路径都代表一个数字：
 * @version 1.0
 * @date 2021/12/19 13:47
 * 二刷，经典题，面试题
 */
public class sumNumbers {
    int sum = 0;

    public static void main(String[] args) {
        new sumNumbers().sumNumbers(TreeNodeUtil.getBT(new Object[]{1, null, 5}));
        new sumNumbers().sumNumbers1(TreeNodeUtil.getBT(new Object[]{4,9,0,5,1}));
    }

    public int sumNumbers(TreeNode root) {
        if (root == null) return sum;
        StringBuilder sb = new StringBuilder();
        sumLeaf(root, sb);
        return sum;
    }

    // 解题思路：深度优先遍历
    private void sumLeaf(TreeNode root, StringBuilder sb) {
        sb.append(root.val);
        if (root.left == null & root.right == null) {
            sum += Integer.valueOf(sb.toString());
            // 到达叶子节点后，这个叶子节点被使用后，要删除这个节点值
            sb.deleteCharAt(sb.length() - 1);
            return;
        }
        if (root.left != null) sumLeaf(root.left, sb);
        if (root.right != null) sumLeaf(root.right, sb);
        // 当前节点 左右节点全部 用过后，要删除该节点
        sb.deleteCharAt(sb.length() - 1);
    }

    // 优化上面的解法
    public int sumNumbers1(TreeNode root) {
        int preSum = 0;
        return dfs(root, preSum);
    }

    private int dfs(TreeNode root, int preSum) {
        if (root == null) return 0;
        // 将preSum 扩大10倍，再加上 root.val
        int nodeSum = preSum * 10 + root.val;
        // 到叶子节点就返回 sum，没到叶子节点就一直往下递归
        if (root.left == null && root.right == null) return nodeSum;
        else return dfs(root.left, nodeSum) + dfs(root.right, nodeSum);
    }
}
